package com.leetcode.partition4;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/9/16 18:15
 */
public class LC329矩阵中的最长递增路径 {

    private static final int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public static int longestIncreasingPath(int[][] matrix) {
        return topological(matrix);
    }

    public static void main(String[] args) {
//        int[][] matrix = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
//        int[][] matrix = {{7, 8, 9}, {9, 7, 6}, {7, 2, 3}};
        int[][] matrix = {{3, 4, 5}, {3, 2, 6}, {2, 2, 1}};
        System.out.println(longestIncreasingPath(matrix));
    }

    private static int topological(int[][] matrix) {
        //统计所有点的出度，如果出度为0，则将点加入到队列
        int[][] outDegree = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                for (int[] dir : dirs) {
                    int x = dir[0] + i, y = dir[1] + j;
                    if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[i].length || matrix[x][y] >= matrix[i][j]) continue;
                    outDegree[i][j]++;
                }
            }
        }
        //将所有出度为0的点加入到队列
        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < outDegree.length; i++) {
            for (int j = 0; j < outDegree[i].length; j++) {
                if (outDegree[i][j] == 0) queue.addLast(new int[]{i, j});
            }
        }
        //拓扑序列的层数就是最大的递增路径
        int answer = 0;
        while (!queue.isEmpty()) {
            answer++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.pollFirst();
                for (int[] dir : dirs) {
                    int x = cur[0] + dir[0], y = cur[1] + dir[1];
                    if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[x].length || matrix[x][y] <= matrix[cur[0]][cur[1]]) continue;
                    outDegree[x][y]--;
                    if (outDegree[x][y] == 0) queue.addLast(new int[]{x, y});
                }
            }
        }
        return answer;
    }

    private static int dynamicProgramming(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int answer = 0;
        //问题转化为寻找有向图的最长路径
        int[][] memo = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                answer = Math.max(answer, memoization(i, j, matrix, memo));
            }
        }
//        Arrays.stream(memo).forEach(item -> System.out.println(Arrays.toString(item)));
        return answer;
    }

    private static int memoization(int row, int column, int[][] matrix, int[][] memo) {
        if (memo[row][column] != 0) return memo[row][column];
        ++memo[row][column];

        for (int[] dir : dirs) {
            int newRow = row + dir[0], newColumn = column + dir[1];
            if (newRow >= 0 && newRow < matrix.length && newColumn >= 0 && newColumn < matrix[0].length && matrix[newRow][newColumn] > matrix[row][column]) {
                memo[row][column] = Math.max(memo[row][column], memoization(newRow, newColumn, matrix, memo) + 1);
            }
        }
        return memo[row][column];
    }
}
